Corelab Seminar
2016-2017
Abhi Shelat
Verifiable outsourcing for hardware
Abstract.
A manufacturer of custom hardware (ASICs) can undermine the intended execution of that hardware; high-assurance execution thus requires controlling the manufacturing chain. However, a trusted platform might be orders of magnitude worse in performance or price than an advanced, untrusted platform. This talk initiates exploration of an alternative: using verifiable computation (VC), an untrusted ASIC computes proofs of correct execution, which are verified by a trusted processor or ASIC. In contrast to the usual VC setup, here the prover and verifier together must impose less overhead than the alternative of executing directly on the trusted platform.
We instantiate this approach by designing and implementing physically realizable, area-efficient, high throughput ASICs (for a prover and verifier), in fully synthesizable Verilog. Our first system, called Zebra, is based on the CMT and Allspice interactive proof protocols, and with careful design, and attention to architectural challenges, can meet or exceed the performance of executing directly on the trusted platform for a class of computations (ignoring the cost of pre computation).
Our second system, called Giraffe, charges Giraffe for all costs (including pre-computation) and identifies regimes where outsourcing is worthwhile. Giraffe's base is a new interactive proof geared to data parallel computation which we prove to be \emph{asymptotically optimal} for the prover, i.e., for a large enough batch size, the prover’s running time is linear in the total number of gates in the arithmetic circuit (whereas prior work incurs an extra log(width of circuit) factor). Giraffe wins even when outsourcing several tens of sub-computations, scales to $500\times$ larger computations than prior work, and can profitably outsource \emph{parts} of programs that are not worthwhile to outsource in full.
Joint work with Riad Wahby, Max Howland, Sid Garg, Michael Walfish, and Ye Ji, Andrew J Blumberg, Justin Thaler, Thomas Wies.